package 搜索算法.广度优先搜索;

import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.Deque;
import java.util.List;

/**
 * 1. 问题描述
 *      n块石头放置在二维平面中的一些整数坐标点上。每个坐标点上最多只能有一块石头。
 *      如果一块石头的 同行或者同列 上有其他石头存在，那么就可以移除这块石头。
 *      给你一个长度为 n 的数组 stones ，其中 stones[i] = [xi, yi] 表示第 i 块石头的位置，返回 可以移除的石子 的最大数量。
 *
 * 2. 算法分析
 *      BFS实现(广度优先搜索，非递归实现)
 *
 * 3. 代码实现
 */
@SuppressWarnings("all")
public class 移除最多的同行或者同列的石头 {

    public int removeStones(int[][] stones) {
        int stoneCounts = stones.length;
        List<List<Integer>> edges = new ArrayList<>();
        // 初始化边信息
        for (int i = 0; i < stoneCounts; i++) {
            List<Integer> temp = new ArrayList<>();
            edges.add(temp);
            for (int j = 0; j < stoneCounts; j++) {
                if ((stones[i][0] == stones[j][0]) || (stones[i][1] == stones[j][1])) {
                    edges.get(i).add(j);
                }
            }
        }
        // 采用栈模拟
        Deque<Integer> stack = new ArrayDeque<>();
        int connectionCounts = 0;
        boolean[] visited = new boolean[stoneCounts];
        for(int x = 0; x < stoneCounts; x++) {
            if(visited[x] == false) {
                stack.add(x);
                visited[x] = true;
                while(!stack.isEmpty()) {
                    int cur = stack.pop();
                    for(int y : edges.get(cur)) {
                        if(visited[y] == false) {
                            stack.add(y);
                            visited[y] = true;
                        }
                    }
                }
                connectionCounts++;
            }
        }
        return stoneCounts - connectionCounts;
    }
}
